import java.util.Scanner;

public class 数的潜能 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        // a 3的数量，b 2的数量
        long a = 0;
        int b = 0;
        int[] x = new int[100];
        long[] z = new long[100];
        // a 3的数量，b 2的数量
        if (n % 3 == 1) {
            a = (n / 3) - 1;
            b = 2;
        } else if (n % 3 == 2) {
            a = n / 3;
            b = 1;
        } else {
            a = n / 3;
        }
        // c a个3相乘取模的当前位置 x[]与z[]记录相应的取模值及取模位置，d 后一半剩余相乘数量。
        long c = 1;
        int yu = 3 % 5218;
        int k = 0;
        x[0] = yu;
        z[0] = c;
        while (a >= 2 * c) {
            yu = (yu * yu) % 5218;
            x[++k] = yu;
            c *= 2;
            z[k] = c;
        }
        long d = a - c;
        for (int i = k - 1; i >= 0; i--) {
            if (d > z[i]) {
                yu = (yu * x[i]) % 5218;
                d = d - z[i];
            }
        }
        yu = (int) ((yu * Math.pow(3, d) * Math.pow(2, b)) % 5218);
        System.out.print(yu);
    }
}